package leetcode.D2000.T1081;

import java.util.Deque;
import java.util.LinkedList;

class Solution {
//    public String smallestSubsequence(String s) {
//        StringBuilder sb = new StringBuilder();
//        Deque<Character> dq = new LinkedList<>();
//        boolean[] inStack = new boolean[256];
//        int[] count = new int[256];
//        for(int i=0; i<s.length(); ++i) {
//            count[s.charAt(i)]++;
//        }
//        for(int i=0; i<s.length(); ++i) {
//            char c = s.charAt(i);
//            count[c]--;
//            if(inStack[c] == true) {
//                continue;
//            }
//            while (inStack[c] == false && !dq.isEmpty() && dq.getLast() > c) {
//                if (count[dq.getLast()] == 0) {
//                    break;
//                }
//                inStack[dq.removeLast()] = false;
//            }
//            dq.addLast(c);
//            inStack[c] = true;
//        }
//        while(!dq.isEmpty()) {
//            sb.append(dq.removeFirst());
//        }
//        return sb.toString();
//    }

    // 二刷
    public String smallestSubsequence(String s) {
        int[] count = new int[26];
        boolean[] has = new boolean[26];
        Deque<Character> dq = new LinkedList<>();
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            count[s.charAt(i)-'a']++;
        }
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            count[c-'a']--;
            if(has[c-'a']) {
                continue;
            }
            while(!dq.isEmpty() && c < dq.getFirst()) {
                if(count[dq.getFirst()-'a'] == 0) {
                    break;
                }
                has[dq.removeFirst()-'a'] = false;
            }
            dq.addFirst(c);
            has[c-'a'] = true;
        }
        while (!dq.isEmpty()) {
            sb.append(dq.removeLast());
        }
        return sb.toString();
    }
}
